/**
 * @author: shiding
 * @data: 2022/5/23 17:59
 **/
public class LongestPalindrome {

    public static void main(String[] args) {
        String s = "babad";
        String a =  longestPalindrome(s);
        System.out.println("输出："+  a);
    }

    /**
     * 5. 最长回文子串
     * 还是使用 双指针的解法
     * 核心点： 从中心向两端扩散的双指针技巧。  即先确认中心点，
     * 如果回文串的长度为奇数，则它有一个中心字符；如果回文串的长度为偶数，则可以认为它有两个中心字符。所以我们可以先实现这样一个函数：
     * 奇数：一个中心点时： 左右指针 为同一个值
     * 偶数：两个中心点时： 左右指针 为两个不同的值 即： i ，  i + 1;
     *
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            // 以 s[i] 为中心的最长回文子串
            String s1 = palindrome(s, i, i);
            // 以 s[i] 和 s[i+1] 为中心的最长回文子串
            String s2 = palindrome(s, i, i + 1);
            // res = longest(res, s1, s2)
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        return res;
    }

    public static String palindrome(String s, int l, int r) {
        // 防止索引越界
        while (l >= 0 && r < s.length()
                && s.charAt(l) == s.charAt(r)) {
            // 双指针，向两边展开
            l--; r++;
        }
        // 返回以 s[l] 和 s[r] 为中心的最长回文串
        return s.substring(l + 1, r);
    }
}
